\documentclass[utf8, seminar]{ru}
\usepackage{booktabs}

\begin{document}

\title{Uporaba analize glavnih komponenti pri raspoznavanju lica}

\author{Andrija Čajić \and Mateja Čuljak \and Karlo Jež \and Daria Štefić \and Ante Kegalj \and Diana Krušelj-Posavec \and Petra Zadro}

\maketitle

\tableofcontents

\chapter{Uvod}
Čovjek je u stanju kroz cijeli svoj životni vijek prepoznavati tisuće viđenih
lica, te identificirati prijateljska lica istog trenutka, unatoč godinama razdvojenosti. Ta
vještina je vrlo robusna, usprkos mnogim promjenama i različitim vizualnim 
stimulacijama ovisnima o uvjetima u kojima se lice promatra, o izrazu lica, starenju
ili drugim smetnjama poput naočala, promjene frizure i slično.

Sustavi za raspoznavanje lica su zanimljivi ne samo iz teoretskih razloga, već
i iz praktične primjene. Prepoznavanje lica može se primjeniti na niz problema
u stvarnom svijetu (kao što su na primjer identifikacija zločinaca, kod sigurnosnih 
sustava, u obradi slike i filma, kod interakcije čovjeka i računala, itd.). Nažalost, 
razvoj sustava za raspoznavanje lica je poprilično težak zbog mnogobrojnih 
karakteristika lica.

Upravo taj problem pokušava se riješiti metodom analize glavnih 
komponenti (engl. \emph{Principal Component Analysis}, poznatije kao PCA) kojom
želimo izlučiti samo one karakteristike lica koje su nam bitne za prepoznavanje lica i kodirati 
ih što je efikasnije moguće. Tako bi prilikom dovođenja nove nepoznate slike sustavu 
mogli uspoređivati tu sliku samo po tim karakterističnim značajkama sa ostalim 
slikama poznate klasifikacije iz baze i prema tome vidjeti kojem licu nova slika 
pripada.

Konkretno, PCA omogućuje reduciranje dimenzionalnosti prostora
značajki, tj. eliminaciju redundantnih podataka iz skupa za učenje. Matematički
rečeno, želimo naći svojstvene vektore kovarijacijske matrice skupa slika lica po 
kojima ćemo raspoznavati nove slike lica. Pri tome sliku tretiramo kao točku (ili 
vektor) u prostoru velikih dimenzija. 

% Jedno od važnih pitanja u projektiranju klasifikatora jest odabir dimenzije
% vektora značajki. Povećanjem broja značajki se smanjuje pogreška klasifikacije,
% no prevelikim povećanjem dolazi do prenaučenosti te ukupna kvaliteta
% klasifikatora opada. Stoga je potrebno odabrati niti preveliku niti premalu
% dimenziju vektora značajki. Analiza glavnih komponenti \engl{principal component
% analysis, \emph{PCA}} nam omogućuje reduciranje dimenzionalnosti prostora
% značajki, tj.\ eliminaciju redundantnih podataka iz skupa za učenje.

\chapter{Analiza glavnih komponenti (PCA)}

Metoda PCA (ili Karhunen-Loeve transformacija gdje se koristi kovarijacijska 
matrica) je vrlo dobar alat za određivanje glavnih karakteristika 
skupa podataka, učinkovita je za smanjenje dimenzionalnosti, pa tako i 
prepoznavanje uzoraka. Prednosti ovog  pristupa su što omogućuje učenje, te 
kasnije prepoznavanje novih lica, a i brzina, jednostavnost, kapaciteti primjera koji se 
mogu naučiti, te određena doza osjetljivosti na sitne promjene na slikama lica. 
Manji nedostatak ovog rješenja je ograničenost slika na kojima se može
prepoznavati lice (moraju zadovoljavati neke uvjete koji će biti kasnije navedeni).

Uzorci za raspoznavanje su u našem slučaju vektori dimenzija $N \times N$ gdje
je $N$ dimenzija slika. Takvi uzorci naravno neće biti slučajno distibuirani u tome
velikom prostoru i zato se mogu prebaciti u prostor manje dimenzije gdje će ih biti moguće 
isto tako dobro odijeliti. Cilj nam je naći vektore koji će definirati prostor manjih 
dimenzija u kojem će se uzorci moći dobro razdvajati (u našem primjeru se taj prostor 
naziva ``prostor lica''). Kod raspoznavanja lica te vektore
(budući da su to svojstveni vektori kovarijacijske matrice izvornih slika, a i
izgledaju kao lica)
%-- vidi sliku 3)  FIXME koju sliku???
nazivamo ``svojstvena lica''. U sljedećem odlomku opisano je traženje
odgovarajućih svojstvenih lica za dane uzorke, a zatim klasifikacija novih lica
pomoću dobivenih svojstvenih lica.

\section{Računanje svojstvenih lica}
Imamo skup uzoraka $\{\mathbf{x}_i\}_{i=1}^{M}$ gdje je $M$ broj uzoraka. Prvi
korak PCA postupka je ``usrednjavanje uzoraka,'' tj.\ posmicanje uzoraka u prostoru tako da im
srednja vrijednost iznosi nula (0). Postupak se provodi tako da se od svakog
uzorka oduzme srednja vrijednost svih komponenti. Srednja vrijednost svih
komponenti se dobiva izrazom
$$\bar{\mathbf{x}} = \frac{\sum_i^M \mathbf x_i}{M},$$
pri čemu je $M$ kardinalitet skupa $\Omega$ (broj uzoraka), a $\mathbf x_i$ element tog skupa.
Nakon izračuna $\bar{\mathbf{x}}$, posmicanje uzoraka se vrši oduzimanjem srednje vrijednosti od svakog
uzorka, odnosno provodimo:
$$\mathbf{s} = \mathbf x - \bar{\mathbf{x}},\, \forall \mathbf x \in \Omega .$$

Srednje lice našeg skupa slika lica prikazano je na slici \ref{fig:sred}.
Sada želimo naći skup M ortonormalnih vektora un koji najbolje opisuju razdiobu 
podataka. k-ti vektor, $\mathbf{u}_k$, odabire se tako da izraz
$$ \mathbf{\lambda}_k=\frac{1}{M}\sum_{n=1}^{M}(\mathbf{u}_k^T \mathbf{s}_n)^2$$
postiže maksimum pri čemu je
$$ \mathbf{u}_l^T \mathbf{u}_k=\delta_{lk}= \left \{
\begin{array}{cc}
1 , & l=k \\
0 , & \text{inače}\\
\end{array}
\right.$$
Vektori $\mathbf{u}_k$ i skalari $\lambda_k$ su svojstveni vektori i svojstvene
vrijednosti, respektivno, kovarijacijske matrice
$$ C=\frac{1}{M}\sum_{i=1}^M \mathbf{s}_n \mathbf{s}_n^T = AA^T$$
gdje je matrica $A = [\mathbf{s}_1 \mathbf{s}_2 \ldots \mathbf{s}_M]$.

Matrica $C$ je dimenzija $N^2 \times N^2$ pa prema tome postoji $N^2$ parova
svojstvenih vrijednosti i svojstvenih vektora te matrice. Međutim kada vrijedi
$M<N^2$ (tj. kada je broj uzoraka manji od dimenzionalnosti prostora) računanje
svih tih parova je nepotrebno. Tada postoji samo $M-1$ značajnih svojsvenih
vektora (ostali svojstveni vektori imaju pridružene svojstvene vrijednosti jednake nuli). 
Dakle, promatramo svojstvene vektore $\mathbf{v}_l$ matrice $C$ takve da
vrijedi:
$$A^T A \mathbf{v}_l=\mu_l \mathbf{v}_l$$
Pomnožimo li ovaj izraz sa matricom $A$ dobivamo:
$$A A^T A \mathbf{v}_l=\mu_l A \mathbf{v}_l$$
Iz čega vidimo da su $A\mathbf{v}_l$ svojstveni vektori matrice $C$.
Prema tome, gradimo matricu $L = A^T A$ koja je dimenzija $M \times M$ i tražimo $M$ svojstvenih vrijednosti matrice $L$ (umjesto $N^2$ svojstvenih
vrijednosti matrice $C$). Ti svojstveni vektori određuju linearnu
kombinaciju $M$ lica iz skupa za učenje koja će tvoriti svojstvena lica
$\mathbf{u}_l$:
$$\mathbf{u}_l=\sum_{k=1}^M \mathbf{v}_{lk}\mathbf{s}_k;
\qquad l=1 \ldots M$$
Na ovaj način je računanje uvelike smanjeno - sa dimenzije $N^2$ na dimenziju
$M$. U praksi je $M$ mnogo manji od $N$, pa je to vrlo korisno. Pripadne
svojstvene vrijednosti svojstvenih vektora omogućuju i rangiranje svojstvenih vektora po njihovoj korisnosti 
u karakterizaciji varijacija između slika. Za veće pripadne vrijednosti svojstveni vektori 
su od veće važnosti, pa se po potrebi može uzeti i manje od $M$ svojstvenih
vektora. Prostor lica definira se tako sa $M$ (ili manje, npr. $M'$) svojstvenih
vektora i u njega se prebacuju po komponentama $k$ izvorni uzorci
$\mathbf{s}_i$:
$$ \mathbf{s}'_k = \mathbf{u}_k^T \cdot \mathbf{s}_i ;
\qquad k=1 \ldots M'$$
$\mathbf{s}'$ je sada novi uzorak u prostoru lica. Primjetimo da je on sada
mnogo manje dimenzionalnosti $M'$.
\section{Prepoznavanje novog lica}
Želimo li odrediti pripadnost novog uzorka $\mathbf w$, potrebno ga je prvo
projicirati u dobiveni prostor lica u kojem se sada nalaze i izvorni uzorci. Prema sličnoj formuli
kao i za izvorne uzorke (novi uzorak je potrebno još usrednjiti)
dobivamo projicirani novi uzorak $\mathbf w'$:
$$ \mathbf{w}_k' = \mathbf{u}_k^T (\mathbf{w}-\bar{\mathbf x});
\qquad k=1 \ldots M'$$
Kada imamo novi uzorak i izvorne uzorke u istom prostoru odabire se neki
algoritam klasifikacije (načešće je to q-NN klasifikacija opisana u nastavku).
Računanje bilo koje udaljenosti između uzoraka prilikom klasifikacije sada
će biti uvelike olakšano zbog znatne redukcije broja značajki.

%\section{Računanje kovarijacijske matrice uzoraka}
%Kovarijacija je mjera koja se uvijek mjeri između dvije dimenzije, a ukoliko se mjeri između neke dimenzije i nje same, onda je to ustvari njena varijanca (to će biti elementi kovarijacijske matrice na dijagonali). Dakle, da bi smo nekako mogli vidjeti kako pojedina dimenzija vektora ovisi o drugim dimenzijama, koristit ćemo matricu kovarijacija. 

%Kovarijacijska matrica uzoraka ($\mathbf C$) računa se izrazom:
%$$\mathbf C = (c_{ij}),\, c_{ij} = \textrm{cov}(\mathbf x_i, \mathbf x_j),$$
%pri čemu su $\mathbf x_i $ i $\mathbf x_j$ elementi skupa $\Omega $, a $\textrm{cov}(\mathbf x_i, \mathbf x_j)$
%kovarijanca vektora $\mathbf x_i$ i $\mathbf x_j$ definirana kao:
%$$\textrm{cov}(\mathbf x, \mathbf y) = \frac{\sum_{i=1}^n (\mathbf x_i - \bar{\mathbf x})(\mathbf y_i - \bar{\mathbf y})}{n-1},$$
%pri čemu je $n$ dimenzionalnost vektora $\mathbf x$, odnosno $\mathbf y$.

%Kovarijacijska matrica uzoraka zapravo sadrži mjeru kovarijacije između svih uzoraka u skupu uzoraka $\Omega$. Primjerice, ako imamo skup uzoraka $\Omega = \{\mathbf x_1, \mathbf x_2, \mathbf x_3 \}$ tada je kovarijacijska matrica:
%$$\mathbf C = 
%\left( {\begin{array}{ccc}
% \textrm{cov}(\mathbf x_1, \mathbf x_1) & \textrm{cov}(\mathbf x_1, \mathbf x_2) & \textrm{cov}(\mathbf x_1, \mathbf x_3)  \\
% \textrm{cov}(\mathbf x_2, \mathbf x_1) & \textrm{cov}(\mathbf x_2, \mathbf x_2) & \textrm{cov}(\mathbf x_2, \mathbf x_3)  \\
% \textrm{cov}(\mathbf x_3, \mathbf x_1) & \textrm{cov}(\mathbf x_3, \mathbf x_2) & \textrm{cov}(\mathbf x_3, \mathbf x_3)  \\
% \end{array} } \right).
%$$
%Prilikom računanja dobro je znati da vrijedi
%$$\textrm{cov}(\mathbf x, \mathbf y) = \textrm{cov}(\mathbf y, \mathbf x),$$
%odnosno, $\mathbf C$ je dijagonalno simetrična kvadratna matrica.

%\section{Računanje svojstvenih vektora}
%Kod linearnih transformacija množenje vektora kvadratnom matricom mijenja njegovu vrijednost i orijentaciju. Transformacija određenih vektora matricom utječe samo na njihovu vrijednost dok orijentacija ostaje ista. Takve vektore nazivamo svojstvenim vektorima matrice.

%Transformacija svojstvenog vektora skalira njegovu vrijednost za određeni faktor koji nazivamo svojstvena vrijednost ($\lambda$). Ako je svojstvena vrijednost negativna mijenja se smjer, ali ne i orijentacija vektora. Za svaku distinktivnu svojstvenu vrijednost $\lambda$ postoji barem jedan svojstveni vektor $\mathbf{u}$ koji odgovara $\lambda$. Zajedno čine svojstveni par $(\lambda,\, \mathbf{u})$. Kvadratna matrica ne mora imati svojstvene vektore, ali ako postoje ima ih $n$, pri čemu je $n$ broj redaka, odnosno stupaca matrice te su ti vektori međusobno okomiti.

%Svojstveni par $(\lambda, \mathbf u)$ tražimo tako da izraz
%$$\lambda_k = \frac{1}{M}\sum_{n=1}^M(\mathbf u_k^T \bar{\mathbf x})^2$$
%postiže maksimum, s time da je
%$$\mathbf u_l^T \mathbf u_k = \left \{
%\begin{array}{cc}
%1, & l=k \\ 0, & \text{inače}\\
%\end{array}
%\right.$$
%a $\bar{\mathbf x}$ je usrednjeni uzorak. Vektor $\mathbf u_k$ je svojstveni vektor kovarijacijske matrice, a $\lambda_k$ je njegova pripadajuća svojstvena vrijednost.

%Formalno, ako je $\mathbf{A}$ linearna transformacija, ne-nul vektor $\mathbf{u}$ je svojstveni vektor od $\mathbf{A}$ ako postoji skalar $\lambda$ takav da je
%$$\mathbf{A}\mathbf{u} = \lambda \mathbf{u}$$
%Skalar $\lambda$ je svojstvena vrijednost od $\mathbf{A}$ koja odgovara svojstvenom vektoru $\mathbf{u}$.

%\section{Odabir komponenti i izgradnja skupa}
%Kovarijantna matrica je kvadratna te se mogu izračunati njezini svojstveni vektori i vrijednosti. Dobivenom matricom svojstvenih vektora $\mathbf{V}$ dijagonalizira se kovarijantna matrica $\mathbf{C}$
%    $$ \mathbf{V}^{-1}\mathbf{CV}=\mathbf{D} $$
%pri čemu je $\mathbf{D}$ dijagonalna matrica svojstvenih vrijednosti od $\mathbf{C}$. Matrica $\mathbf{D}$ ima oblik $n \times n$ dijagonalne matrice gdje je
%    $$\mathbf D_{pq}=\lambda_m \qquad \text{za } p=q=m$$
%$m$-ta svojstvena vrijednost kovarijantne matrice $\mathbf{C}$ i $\mathbf D_{pq}=0$, za $p \neq q.$

%Matrica $\mathbf{V}$ ima dimenzije $n \times n$ te su stupci matrica $\mathbf{C}$ i $\mathbf{V}$ poredani i upareni. Stupci matrice svojstvenih vektora $\mathbf{V}$ i dijagonalne matrice svojstvenih vrijednost $\mathbf{D}$ sortiraju se prema svojstvenoj vrijednosti od najveće prema najmanjoj pri čemu se obraća pozornost na ispravan redoslijed parova stupaca u obje matrice.

%Svojstveni su vektori sada poredani po važnosti pa se može smanjiti dimenzija podataka odabirom samo prvih $L$ stupaca od $\mathbf{V}$. Za odabir konačnog broja dimenzija može se upotrijebiti usporedba suma svojstvenih vrijednosti prije i poslije smanjivanja broja dimenzija te odrediti prag za određivanje granice $L$. Primjerice:
%    $$g_m = \displaystyle\sum\limits_{q=1}^m \mathbf D_{qq}
%    \qquad \text{za } m=1,\ldots,n$$
%odabiremo prag od 90\%:
%    $$ \frac{g_{m=L}}{g_{m=n}} \geq 90\% $$

%Posljednji je korak PCA množenje izvornog skupa podataka sa svojstvenom matricom.
%    $$ \mathbf{KonacniPodaci} = \mathbf{V}^T \times \mathbf{Podaci}^T + \bar{\mathbf x}$$
    

\chapter{Klasifikacija}

Nakon provedene redukcije dimenzjia vektora značajki novom nepoznatom predstavljenom uzorku, na redu je provođenje klasifikacije, tj. određivanje u koju 
poznatu skupinu lica spada novo lice. To ćemo provoditi klasifikacijskim pravilom najbližeg susjeda \engl{Nearest Neighbor, \emph{NN}}.

\section{q-NN klasifikacija}
Opišimo prvo najjednostavniji slučaj \emph{q-NN} klasifikacije, a to je
\emph{1-NN}. Kod \emph{1-NN} klasifikacije gleda se najveća sličnost nepoznatog
uzorka sa samo jednim uzorkom iz skupa uzoraka sa poznatom klasifikacijom.

Raspolažemo sa skupom uzoraka s poznatom klasifikacijom $\{\vec{\mathbf s_1},
\vec{\mathbf s_2}, \ldots, \vec{\mathbf s_N} \}$ i svaki od tih uzoraka pripada
jednom od razreda $\vec{\omega_1}, \vec{\omega_2}, \ldots, \vec{\omega_M}$.

Tada nepoznati uzorak $\mathbf x$ pripada razredu $\omega_k$ ako $\mathbf s_i$, najbliži susjed uzorku $\mathbf x$ pripada razredu $\omega_k$:
$$D(\vec{\mathbf s_i}, \vec{\mathbf x}) = \min_l\{D(\vec{\mathbf s_i}, \vec{\mathbf x})\},\qquad l = 1, 2, \ldots, N;	\vec{\mathbf s_i} \in \{\vec{\mathbf s_1},
\vec{\mathbf s_2}, \ldots, \vec{\mathbf s_N} \}$$ 
\emph{D} je općenito oznaka za neku mjeru udaljenosti definiranu u prostoru
značajki (Euklidska udaljenost, Mahalanobisova udaljenost, Čebiševljeva udaljenost...). U našem slučaju sličnost između uzoraka ćemo mjeriti Euklidskom udaljenošću 
i udaljenošću preko izračunatih vrijednosti kosinusa kuta između dva vektora  \engl{
-similarity}, koje će biti opisane u nastavku.

Kod 1-NN pravila za klasifikaciju koristio se samo najbliži susjed, ali općenito
za klasifikaciju se može koristiti $q (q>1)$ najbližih susjeda uzorku
$\vec{\mathbf x}$ ($q$ se odabire tako da ne bude višekratnik broja razreda).

Postupak se provodi na sljedeći način: na temelju $q$ uzoraka utvrđuje se broj
vektora $q$ koji pripadaju razredu $\omega_i$, $i = 1, 2, \ldots, M$. (Vrijedi $\sum_i q_i = q$.)
Razvrstaj $\vec{\mathbf x}$ u razred $\omega_k$ za koji vrijedi da je $q_k$
maksimalan.

Pravila klasifikacije 1-NN i $q$-NN su za slučajeve kad su skupovi uzoraka za
učenje veliki vrlo djelotvorna. Međutim, problem kod predstavlja kompleksnost
izračuna udaljenosti i traženja $q$ (ili 1) najbližih udaljenosti. Problem je
još izraženiji za veliku dimenzionalnost prostora značajki, što ovdje nije
slučaj budući da metodom PCA reduciramo broj značajki.

\section{Mjere udaljenosti}
Mjere udaljenosti (ili sličnosti) određuju udaljenost dvaju vektora u prostoru.
Ako je $d$ udaljenost, tada $d(\mathbf a, \mathbf b)$ mora imati sljedeća svojstva \citep{duda2001pattern}:
\begin{description}
\item[Ne negativnost:] $d(\mathbf a, \mathbf b) \geq 0$
\item[Refleksivnost:] $d(\mathbf a, \mathbf b) =  0 \text{ ako i samo ako } \mathbf a = \mathbf b$
\item[Simetričnost:] $d(\mathbf a, \mathbf b) =  d(\mathbf b, \mathbf a)$
\item[Nejednakost trokuta:] $d(\mathbf a, \mathbf b) + d(\mathbf b, \mathbf c) > d(\mathbf a, \mathbf c)$
\end{description}   

\subsection{Euklidska udaljenost}
Euklidska udaljenost između točaka $\vec{\mathbf x}$ i $\vec{\mathbf y}$ u
\emph{n}-dimenzionalnom prostoru definirana je na sljedeći način:
$$d(\mathbf x, \mathbf y) = ||\vec{\mathbf x} - \vec{\mathbf y}|| =
\sqrt{\sum_{i=1}^n(\mathbf x_i - \mathbf y_i)^2}.$$

\subsection{Udaljenost preko kosinusa}
\emph{Cosine-similarity} je mjera sličnosti između dva vektora u \emph{n}-dimenzionalnom
prostoru koja se dobiva tako da se računa kosinus kuta između njih. Imamo li dva
vektora $\mathbf{x}$ i $\mathbf{y}$, definirana je na sljedeći način:
$$\cos(\theta) = \frac{\mathbf x \cdot \mathbf y}{||\mathbf x||\cdot || \mathbf y ||}.$$

Rezultat sličnosti kreće se od vrijednosti $-1$ (što znači da su vektori suprotni)
do 1 (što znači da su potpuno isti). Rezultat 0 indicira nezavisnost, a sve
ostale vrijednosti između predstavljaju sličnost, odnosno različitost vektora.

\subsection{"City block'' udaljenost}
Ova udaljenost je poznata i pod nazivom ''Manhattan'' udaljenost jer računa 
udaljenost na način da zbraja apsolutne vrijednosti razlika po komponentama. 
Formula glasi:
$$d(\mathbf x, \mathbf y) = \sum_{i=1}^n|\mathbf x_i - \mathbf y_i|$$

\chapter{Raspoznavanje lica}

Ideja rješavanja zadanog problema je da se slika lica projicira na prostor
značajki koji prikazuje raspon bitnih varijacija među već poznatima prikazima lica, tzv.
``prostor lica''. Taj mali skup bitnih značajki se naziva ``eigenfaces'' tj.\
svojstvena lica, i oni predstavljaju svojstvene vektore skupa lica. Skup podataka
poznatih lica tvori skup za učenje. Projekcija lica karakterizira lice kao
težinsku sumu svojstvenih vektora, tako da se za raspoznavanje uspoređuje
dobivena suma sa već poznatim primjerima. Lice se, dakle, klasificira
uspoređivanjem njegovog položaja u prostoru lica s položajem poznatih primjera.

\section{Baza lica}
Problemu raspoznavanja
lica se pristupa kao raspoznavanju $2D$ slika, bez potrebe za rekonstruiranjem
$3D$ modela iz danih slika, podrazumijevajući da su dani primjeri fotografirani na
odgovarajući način, tako da mogu biti opisani skupom $2D$ karakteristika. Uvjeti za
raspoznavanje:
\begin{itemize}
  \item lica su uspravna,
  \item na slikama je provedena geometrijska i svjetlosna normalizacija,
  \item lica gledaju ravno u kameru.
\end{itemize}

Baza lica koju smo koristili, sastoji se od 295 različitih lica. Za svako lice
postoje četiri snimanja, a svako snimanje daje dvije slike. Slike smo
rasporedili u dva skupa, jedan za učenje, a drugi za testiranje. Slike smo
rasporedili tako da smo prvo i drugo snimanje smjestili u skup za učenje, a
treće i četvrto u skup za testiranje (u svakom skupu po četiri slike svakog
lica). Slike su dimnenzija $64 \times 64$, što znači da će  biti predstavljene
kao uzorci u 4096-dimenzionalnom prostoru. Vrijednosti značajki su vrijednosti sive razine
svakog piksela slike predstavljene cijelim brojevima 0-255.
Slika \ref{fig:lice} je primjer lica iz baze koji smo koristili.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\textwidth]{jedno.jpg}
  \end{center}
  \caption{Primjer slike lica iz baze.}
  \label{fig:lice}
\end{figure}

\section{Modeliranje sustava}
\label{sec:modeliranje}
 Prvo radimo inicijalizaciju sustava:
\begin{enumerate}
  \item Učitava se skup slika za učenje.
  \item Računaju svojstveni vektori na osnovu svih uzoraka iz skupa za
  učenje. Zatim se sačuva samo određen postotak svojstvenih vektora,
  uzimajući one sa boljim vrijednostima. Odabranim svojstvenim vektorima se
  definiraju svojstvena lica.
  \item Sva lica iz skupa za učenje projiciraju se u prostor
  svojstvenih lica. Time smo postigli smanjenje vektora značajki uzoraka.
\end{enumerate}
Nakon što smo uspješno inicijalizirali sustav, za prepoznavanje novog lica provodi se sljedeći postupak:
\begin{enumerate}
   \item  Nova ulazna slika, iz skupa za testiranje, projicira se u prostor
   svojstvenih lica.
   \item  Dobiveni uzorak se, nekom od metoda klasifikacije, pokušava svrstati u
   neku od klasa, tj. pridružiti se nekom od već poznatih lica.
\end{enumerate}

Koji postotak svojstvenih vektora uzeti se određuje ekspreimentiranjem, ovisno o
odabranom načinu klasifikacije, provjerava se sa kojim najmanjim postotkom
svojstvenih vektora se dobivaju najbolji rezultati.
Uspješnost raspoznavanja određuje se provođenjem
klasifikacije svih uzoraka iz skupa za testiranje, pritom brojeći uspješne, tj. neuspješne klasfikacije. 

Prikaz dijagrama toka primjera provedbe PCA prilikom raspoznavanja lica
može se vidjeti na slici \ref{fig:alg}.

\begin{figure}
  \begin{center}
    \includegraphics[width=6.5cm]{algoritam.png}
  \end{center}
  \caption{Dijagrama toka postupka prepoznavanja lica.}
  \label{fig:alg}
\end{figure}

\section{Implementacija}

Postupak je implementiran u \emph{Matlab}u. 
Prije pokretanja programa, potrebno je bazu lica rasporediti u mape za učenje i testiranje. Prilikom izvršavanja
programa, ispisuje se definirani postotak uzetih značajki, otvara prikaz
srednjeg lica, te najboljeg svojstvenog lica. Na kraju izvršavanja program
ispisuje točnost klasifikacije u obliku postotka točno klasificiranih lica iz
skupa za testiranje.

Slika \ref{fig:sred} prikazuje dobiveno srednje lice, a slika
\ref{fig:svoj} najbolje svojstveno lice.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\textwidth]{srednje.jpg}
  \end{center}
  \caption{Srednje lice dobiveno iz svih slika u bazi.}
  \label{fig:sred}
\end{figure}

\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\textwidth]{svojstveno.jpg}
  \end{center}
  \caption{Najbolje izračunato svojstveno lice.}
  \label{fig:svoj}
\end{figure}

%	NATUKNICA:		ovdje treba pogledati kako da se zapišu ovi nazivi skripti, ja sam ih trenutno samo nabrojala
%\newline
Skripte napisane u matlabu za provođenje postupaka opisanih u poglavlju \ref{sec:modeliranje} definirane su na sljedeći način. Iz glavne skripte Pokreni.m pokreće se osnovni program.  U njemu se redom pozivaju skripte: Ucitaj('ucenje'); PCA(M, 90); ProjekcijaUzoraka(US, SL); KlasificirajSve('testiranje', SL, PU, sredina, kl, 1, 'cityblock');

Prva skripta učitava redom slike iz skupa za učenje koji je ujedno i jedini ulazni argument, te ih pretvara u vektore. Iz tih vektora stvaramo matricu u kojoj su onda pohranjeni vektorski zapisi svih slika. Matrica u kojoj su pohranjene sve slike je dvodimenzionalna, svaki stupac je vektor jedne slike, a budući da jedna slika ima $64 \times 64$ pixela te ima 1180 slika, matrica je dimenzija 
$(N \times N) \times M = (64  \times 64) \times 1180) = (4096 \times 1180)$.

Kao izlazni argument te skripte je opisana matrica slika i vektor koji sadrži informaciju o pripadnosti svakog uzorka određenoj klasi. Klase su definirane kao pojedina slika, svaka osoba ima svoj niz znakova koji je početak svih naziva slika te osobe.

% NATUKNICA		ne znam kako da označavam skripte, naglašeno, pod navodnicima... za sad je pod navodnicima ako to nije u redu, neka netko to onda popravi, slično vrijedi za ove veličine matrica koje mislim da su bitne i da ih se ne bi trebalo micati
Osnovna skripta projekta "PCA.m" poziva se sljedeća iz glavne skripte "Ucitaj.m". To je osnovna funkcija koja obrađuje uzorke za učenje i radi analizu glavnih komponenti za te uzorke. Ulazni argumenti su matrica koju smo dobili iz svih ulaznih slika $(N \times N) \times M$ i broj znacajki koji označava koliko značajki će se uzimati od ukupno mogućih $(M-1)$. 

Svojstveni vektori originalnog prostora mogu se računati na dva načina. Budući da imamo $M$ uzoraka što je mnogo manje od $N\cdot N$, umjesto traženja svojstvenih vektora kovarijacijske matrice koja bi bila veličine $N\cdot N$, pri čemu je $N$ broj značajki u našem slučaju broj pixela, tražimo $(M-1)$ svojstvenih vektora preko matrice $\text{usrednjeniUzorci}'\cdot \text{usrednjeniUzorci}$, odnosno preko korelacijske matrice. Ostalih $N\cdot N-(M-1)$ bi ionako imalo svojstvene vrijednosti 0.

Na temelju matrice slika radi se nova matrica koja nastaje usrednjavanjem svih uzoraka, odnosno oduzima im se srednja vrijednost svih uzoraka po značajkama, te na temelju nje iz sortirane matrice svojstvenih vrijednosti izabire broj značajki koje najviše dopirnose raspršenju slika iz ulaznog skupa.  Cilj ovog postupka je naravno smanjiti broj dimenzija ulaznog prostora zadržavajući samo one vrijednosti koje najviše doprinose razlikovanju odnosno raspršenosti ulaznih primjera u njihovom originalnom prostoru.
 
Kao izlazni argumenti skritpe "PCA.m" dobijamo vektor srednjih vrijednosti svih značajki iz skupa za učenje, matricu ulaznih uzoraka, ali usrednjene, znači oduzete su im srednje vrijednosti po značajkama te svojstvena lica dobivena množenjem sa odabranim brojem najvažnijih svojstvenih vektora, veličine $(N\cdot N) \times R$ gdje je $R\leq M-1$.

Svojstveni vektori koji odgovaraju odabranim svojstvenim licima množe se sa svim uzorcima iz skupa za učenje, odnosno sa matricom vektora slika, na temelju čega se dobije ulazni skup transformiran na prostor manjih dimenzija od izvornog, koji razpinje odabran broj najvažnijih vektora. Taj skup, odnosno vektori transformirane matrice ulaznih slika nazivaju se svojstvena lica. Ovaj dio posla obavlja jednostavna skripta "ProjekcijaUzoraka.m".

Na kraju ostaje još samo klasificirati slike iz skupa za testiranje prema svojstvenim licima koja su dobivena iz skupa za učenje. U jednostavnoj for petlji koja pritom broji ispravno odnosno neispravno klasificirane uzorke, pozivaju se već postojeće funkcije u \emph{Matlabu} koje vraćaju klasu kojoj je ispitivana slika najbliža u transformiranom prostoru značajki. Klasa se određuje prema željenom broju najbližih uzoraka u transformiranom prostoru. Ako su to slike iste osobe, klasifikacija je ispravna, u protivnom je klasifikacija neispravna.

Korištenje i rezultati pojedinih algoritama za traženje najbližih svojstvenih lica u transformiranom prostoru opisani su tablicama i rezultatima u poglavlju \ref{sec:rezultati}.

\chapter{Rezultati}
\label{sec:rezultati}
Prvo je na podijeljenim skupovima za učenje i testiranje (na prethodno opisan način)
proveden postupak  klasifikacije 1-NN (korištenjem Euklidske udaljenosti) bez primjene 
PCA metode. Za velike ulazne skupove to je trajalo duže vrijeme i postignuta je uspješnost 
klasifikacije 81.1017\%, što je zadovoljavajuće. Problem je što se u ovom
slučaju koristi 4096 dimenzionalan vektor značaji kao prikaz svake slike, pa usporedba svih slika sa novom 
traje duže.

Broj značajki dobiven metodom PCA je 1180. Najbolja uspješnost klasifikacije se postiže za 1-NN klasifikator 
koji koristi cityblock udaljenost, te 90 značajki (postotak uzetih značajki je 7.6271\%). Točnost klasifikacije je tada 84.1525\%, 
što se može vidjeti iz tablice \ref{tab:tablicaKNN}. Korištenjem više od 90
značajki nema znatnijeg utjecaja na uspješnost klasifikacije (npr. korištenjem
1100 značaji uspješnost je 81.0169\% za Euklidsku udaljenost). Grafički je to
prikazano na slici \ref{fig:knn}. Iako, tu vidimo da to nije slučaj i za
City block udaljenost. Iz nekih (nama nepoznatih) razloga, uspješnost klasifikacije uzimanjem sve većeg broja značaki lagano opada, 
dok za Euklidsku i cosinusovu ostaje pri maksimumu. Uzimanjem svih značajki je dakle najbolja Euklidska udaljenost, 
koja se stoga čini prikladnija od City block jer ako i kod optimuma gledamo nije velika razlika u uspješnosti.

Rađeno je i testiranje za različite vrijednosti parametra k za algoritam k-NN. Korišteno je 100 značajki (gdje se sigurno postiže 
maksimum klasifikacije, kako smo prije utvrdili), a vrijednosti za k su uzete do 8-NN (nije bilo potrebno dalje, vidjelo da uspješnost opada). 
Vidi se da je se najbolji rezultati postižu za najmanje k-ove, tj. 1-NN i 2-NN što je i bilo za očekivati s obzirom na odnos broja uzoraka i 
dimenzionalnosti vektora značajki. Vrijednosti za 1-NN i 2-NN su identične budući da kod 2-NN zapravo uzima isto prvi najbliži, pa kod 3-NN 
vidimo da počne padati uspješnost. Za veće k-ove uspješnost dalje lagano opada.
Ovi rezultati su prikazani tablicom \ref{tab:tablicaPCA} i slikom \ref{fig:knn}.

%dodati još zašto kod cityblocka opada a kod drugih ne.


\begin{table*}[!htb]
\caption{Točnosti klasifikatora za razne parametre k i razne udaljenosti. Stupci su točnosti za parametar k u vrijednosti od 1 do 8. Korišteno je 100 značajki.}
\label{tab:tablicaKNN}
\begin{center}
\begin{tabular}{lcccccccc}
\toprule
Udaljenosti & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\midrule \\
euclid 	&  81.01 & 81.01 & 79.57 & 80.08 & 77.71 & 76.01 & 74.74 & 74.74 \\
cosine 	& 	80.33 & 80.33 & 77.88 & 77.20 & 75.67 & 74.49 & 73.30 & 72.20 \\
cityblock &	83.98 & 83.98 & 82.71 & 82.96 & 81.52 & 80.59 & 79.49 & 78.98 \\
%correlation &  80.0847 & 80.0847 & 78.0508 & 77.0339 & 74.9153 & 74.1525 & 72.8814 & 72.3729 \\
\bottomrule
\end{tabular}
\end{center}
\end{table*}

\begin{figure}
  \begin{center}
    \includegraphics[width=\columnwidth]{novapcagraf.jpg}
  \end{center}
  \caption{Graf uspješnosti PCA za različite postotke značajki. Ružičastom bojom je označen cityblock 1-NN, crvenom bojom euklidski 1-NN, plavom bojom kosinus 1-NN, a zelenom bojom korelacijski 1-NN klasifikator.}
  \label{fig:knn}
\end{figure}

\begin{table*}
\caption{Točnosti PCA za razne postotke uzetih značajki uz 1-NN  klasifikator.}
\label{tab:tablicaPCA}

\begin{center}
\begin{tabular}{llcc}
\toprule
Broj značajki & Postotak uzetih značajki & Cityblock & Euclid \\
\midrule \\
50 & 4.2373 & 79.7458 & 78.3051 \\ 
60 & 5.0848 & 81.4407 & 79.7458\\
70 & 5.9322 & 82.1186 & 80.0000 \\
80 & 6.7797 &  82.8814 &  80.9322\\
90 & 7.6271 & 84.1525 & 80.5085\\
100 & 8.4746 & 83.9831 & 81.0169\\
110 & 9.3320 & 84.1525 & 81.1017\\
120 & 10.1695 & 83.8983 & 81.1017\\
130 & 11.0170 & 83.3898 & 81.1017\\
140 & 11.8644 & 83.6441 & 81.1864\\
150 & 12.7119 & 83.5593 & 81.1017 \\ 
160 & 13.5594 & 82.7119 & 80.9322\\
170 & 14.4068 & 82.8814 & 81.1017\\
180 & 15.2543 &  82.6271 & 81.0169\\
190 & 16.1017 & 82.4576 & 81.1017 \\
200 & 16.9492 & 82.2881 & 81.1017\\
300 & 25.4238 & 80.0847 & 81.1017\\
400 & 33.8984 & 77.7966 & 81.1017\\
500 & 42.3730 &  76.6102 & 81.0169 \\
600 & 50.8476 & 75.3390 & 81.1017 \\
700 & 59.3222 & 75.0847 & 80.9322 \\
800 & 67.7968 & 75.3390 & 81.0169 \\
900 & 76.2714 & 75.7627 & 81.0169 \\
1000 & 84.7460 & 76.4407 & 81.0169\\
1100 & 93.2206 & 76.7797 & 81.0169 \\
\bottomrule 
\end{tabular}
\end{center}
\end{table*}

%\begin{figure}
%  \begin{center}
%    \includegraphics[width=\columnwidth]{knn.jpg}
%  \end{center}
%  \caption{Graf uspješnosti PCA za različite postotke značajki. Ružičastom bojom je označen cityblock 1-NN, crvenom bojom euklidski 1-NN, plavom bojom kosinus 1-NN, a zelenom bojom korelacijski 1-NN klasifikator.}
%  \label{fig:knn}
%
%\end{figure}

%
%\begin{figure}
%  \begin{center}
%    \includegraphics[width=\columnwidth]{pcalinija.jpg}
%  \end{center}
%  \caption{Drugi graf uspješnosti PCA za različite postotke značajki.}
%  \label{fig:pca2}
%\end{figure}



\chapter{Zaključak}

Cilj projekta je primijeniti metodu PCA na raspoznavanje lica. Opisani pristup 
prepoznavanju lica preko svojstvenih vektora proizašao je iz ideje da se lice može 
prepoznati na osnovu manje skupine karakteristika lica koje najbolje aproksimiraju 
skupinu poznatih lica. Ključno je da se to radi bez zahtijevanja da te značajne 
karakteristike moraju odgovarati karatkeristikama prema kojima mi ljudi 
prepoznajemo lica (npr. oči, kosa, nos...). Iako ova metoda ne pokriva generalno 
problem prepoznavanja, taj pristup pokazao se u praksi kao praktično rješenje koje je 
vrlo efikasno za konkretni problem prepoznavanja lica.

Postupak se pokazao relativno jednostavan za implementaciju, izvodi se u 
realnom vremenu i uspješnost klasifikacije je dobra uz ograničenja za slike iz 
baze koja su nam prethodno omogućena.

Vidjeli samo da je prepoznavanje lica k-NN 
algoritmom bez primjene PCA dalo približno iste rezultate kao i u slučaju kada je 
primjenjena metoda PCA, ali je izvođenje programa trajajalo znatno duže jer je 
uzorak bio dimenzije 4096, tj. imao je 4096 značajki. Primjenom PCA metode dobili 
smo da je dovoljno raditi klasifikaciju sa samo 90 relevantnih značajki tako da 
uspješnost ostane jednako dobra. Dimenzionalnost prostora je tako smanjena za čak 
45.5 puta, pa je zato i izvođenje programa brže. Time je pokazana izrazita efikasnost 
primjene metode PCA u problemu raspoznavanja lica. 

%Ovaj opisani pristup prepoznavanju lica preko svojstvenih vektora proizašao je
%iz ideje da se lice može prepoznati na osnovu manje skupine karakteristika lica
%koje najbolje aproksimiraju skupinu poznatih lica. Ključno je da se to radi bez
%zahtijevanja da te značajne karakteristike moraju odgovarati karatkeristikama
%prema kojima mi ljudi prepoznajemo lica (npr.\ oči, kosa, nos...). Iako ova
%metoda ne pokriva generalno problem prepoznavanja, taj pristup pokazao se u
%praksi kao praktično rješenje koje je vrlo efikasno za konkretni problem
%prepoznavanja lica. Čini se brzo i relativno jednostavno za implementaciju i
%trebalo bi dobro raditi uz neka ograničenja koja su nam prethodno omogućena
%(normalizirana crno bijela slika, sa centriranim licem koje gleda ravno u
%kameru).



\nocite{gyrgyek1988uvod}
\nocite{pca}
\nocite{cosine}
\nocite{turk1991eigen}
\nocite{faistPrimjena}

\bibliography{literatura}
\bibliographystyle{fer}

\end{document}
